\setcounter{chapter}{2}
\setcounter{section}{2}

\chapter{Chương trình ví dụ}
\textbf{Chương trình minh họa thuật toán bucket sort song song}
\begin{enumerate}
\item Thực hiện song song thuật toán bucket sort bằng cách gán cho mỗi tiến trình một giỏ.\\
$\#$include$<stdio.h>$\\
$\#$include$<mpi.h>$\\
\\
void sort(int ar[], int size)\\
\{\\
\hspace*{1cm}	int temp;\\
\hspace*{1cm}	int i,j;\\
\\
\hspace*{1cm}        for (i$=$size$-$1; i $>=$1; i$--$)\\
\hspace*{2cm}                for (j$=$0; j $<$ i; j$++$)\\
\hspace*{3cm}                       if (ar[j] $>$ ar[j$+$1])\\
\hspace*{3cm}                       \{\\
\hspace*{3.5cm}                                temp $=$ ar[j];\\
\hspace*{3.5cm}                                ar[j]$=$ ar[j$+$1];\\
\hspace*{3.5cm}                                 ar[j$+$1] $=$ temp;\\
 \hspace*{3cm}                       \}\\
\}\\
\\
int main(int argc, char ${}^{*}$argv[])\\
\{\\
\hspace*{1cm}	int rank,p;\\
\hspace*{1cm}	int a,b;\\
\hspace*{1cm}	int n;\\
\hspace*{1cm}	int ${}^{*}$array,${}^{*}$local;\\
\hspace*{1cm}	int ${}^{*}$counters, ${}^{*}$displs;\\
\hspace*{1cm}	int start, end, slice;\\
\hspace*{1cm}	int count,disp,i;\\
\\
\hspace*{1cm}	MPI$\_$Status status;\\
\hspace*{1cm}	MPI$\_$Init($\&$argc,$\&$argv);\\
\hspace*{1cm}	MPI$\_$Comm$\_$size(MPI$\_$COMM$\_$WORLD,$\&$p);\\
\hspace*{1cm}	MPI$\_$Comm$\_$rank(MPI$\_$COMM$\_$WORLD, $\&$rank);\\
	// initialize random number generation\\
\hspace*{1cm}	srand(time(NULL));\\
\hspace*{1cm}	if (rank$==$0)\\
\hspace*{1cm}\{\\
\hspace*{2cm}		    printf("How big should the array be ? ");\\
\hspace*{2cm}			scanf("\%d", $\&$n);\\
\hspace*{2cm}			array $=$ (int ${}^{*}$)malloc(sizeof(int)${}^{*}$n);\\
\hspace*{2cm}			printf("What is the value of a (size of the range): ");\\
\hspace*{2cm}			scanf("\%d", $\&$a);\\
		// fill the array with random numbers\\
\hspace*{2cm}			for (i$=$0; i $<$ n; i$++$)\\
\hspace*{2cm}			\{\\
\hspace*{2.5cm}				array[i] $=$ rand() \% a;\\
\hspace*{2.5cm}				printf(" \%d ", array[i]);\\
\hspace*{2.5cm}			\}\\
\hspace*{2cm}			printf("$\backslash$n");\\		
\hspace*{1cm}		\}\\
	// send array, a, and n\\
\hspace*{1cm}		MPI$\_$Bcast($\&$n,1,MPI$\_$INT, 0, MPI$\_$COMM$\_$WORLD);\\
\hspace*{1cm}		MPI$\_$Bcast($\&$a,1,MPI$\_$INT, 0, MPI$\_$COMM$\_$WORLD);\\	
\hspace*{1cm}		if (rank !$=$ 0)\\
\hspace*{2cm}		array $=$ (int ${}^{*}$)malloc(sizeof(int)${}^{*}$n);\\
\hspace*{1cm}	MPI$\_$Bcast(array, n, MPI$\_$INT, 0, MPI$\_$COMM$\_$WORLD);\\
\hspace*{1cm}	slice $=$ a / p;\\
\hspace*{1cm}	start $=$ rank ${}^{*}$ slice;\\
\hspace*{1cm}	end $=$ (rank $==$p$-$1) ? a : start$+$slice;\\
\hspace*{1cm}	count $=$ 0; \\
\hspace*{1cm}	local $=$ (int ${}^{*}$)malloc(sizeof(int)${}^{*}$n);\\
	// create the local bucket\\
\hspace*{1cm}	for (i$=$0; i $< $n; i$++$)\\
\hspace*{2cm}		if (array[i] < end $\&\&$ array[i] $>=$ start)\\
\hspace*{3cm}			local[count$++$] $=$ array[i];	\\\\
	// local sort the bucket\\
\hspace*{1cm}	sort(local,count);\\
	// Need to compute the displacements\\
\hspace*{1cm}	MPI$\_$Scan($\&$count,$\&$disp,1,MPI$\_$INT,MPI$\_$SUM,MPI$\_$COMM$\_$WORLD);\\
	// Let master Gather the counts and the displacements\\
\hspace*{1cm}	if (rank $==$ 0)\\
\hspace*{2cm}		counters $=$ (int ${}^{*}$)malloc(sizeof(int)${}^{*}$p);\\
\hspace*{1cm}	MPI$\_$Gather($\&$count,1,MPI$\_$INT, counters, 1, MPI$\_$INT, 0, MPI$\_$COMM$\_$WORLD);\\
	// Let master Gather the displacements\\
\hspace*{1cm}	if (rank $==$ 0)\\
\hspace*{1cm}\{\\
\hspace*{2cm}		displs $=$ (int ${}^{*}$)malloc(sizeof(int)${}^{*}$(p$+$1));\\
\hspace*{2cm}		displs[0]$=$0;\\
\hspace*{1cm}\}\\
\hspace*{1cm}	MPI$\_$Gather($\&$disp,1, MPI$\_$INT, displs$+$1, 1, MPI$\_$INT, 0, MPI$\_$COMM$\_$WORLD);\\
\hspace*{1cm}	// gather the sorted buckets\\
\hspace*{1cm}	MPI$\_$Gatherv(local, count, MPI$\_$INT, array, counters, displs, MPI$\_$INT, 0, MPI$\_$COMM$\_$WORLD);\\
\hspace*{1cm}	if (rank $==$ 0)\\
\hspace*{1cm}	\{\\
\hspace*{2cm}		printf("Sorted: ");\\
\hspace*{2cm}		for (i$=$0; i $<$ n ; i$++$)\\
\hspace*{3cm}			printf(" \%d ", array[i]);\\
\hspace*{2cm}		printf("$\backslash$n");\\
\hspace*{1cm}\}\\
\hspace*{1cm}	MPI$\_$Finalize();\\
\}
\item Thực hiện song song thuật toán bucket sort bằng cách chia nhỏ dãy thành $m$ miền con, mỗi miền ứng với một bộ xử lý và mỗi bộ xử lý chứa các giỏ nhỏ hơn.\\
Chương trình bao gồm 6 bước thực hiện như sau:\begin{itemize}
\item Sinh mảng A ngẫu nhiên
\item Phân phối A tới mỗi node
\item Sinh các giỏ con tại mỗi nodes
\item Sắp xếp tại mỗi giỏ trên mỗi nodes
\item Phân phối các giỏ nhỏ tới các node phù hợp
\item Trộn kết quả tại node gốc
\end{itemize}
$\#$include$<stdio.h>$\\
$\#$include$<mpi.h>$\\
$\#$include$ <stdlib.h>$\\

$\#$define root 0\\
$\#$define MCW MPI$\_$COMM$\_$WORLD\\
$\#$define NODES 4\\
$\#$define MATSIZE NODES${}^{*}$10\\

int main(int argc, char ${}^{*}$argv[])\\
\{\\

\hspace*{1cm}	int rank, size, x, y, z, tmp;\\
\hspace*{1cm}	int mat1[MATSIZE] $=$ \{0\};\\
\hspace*{1cm}	int bigbucket[MATSIZE] $=$ \{0\};\\
\hspace*{1cm}	int bucket[NODES][MATSIZE/NODES] $=$ \{\{0\}\};\\
\hspace*{1cm}	int mat2[MATSIZE${}^{*}$NODES] $=$ \{0\};\\
\hspace*{1cm}	int part[MATSIZE/NODES] $=$ \{0\};\\

\hspace*{1cm}	MPI$\_$Init($\&$argc, $\&$argv);\\
\hspace*{1cm}	MPI$\_$Comm$\_$rank(MCW, $\&$rank);\\
\hspace*{1cm}	MPI$\_$Comm$\_$size(MCW, $\&$size);\\

\hspace*{1cm}	if (size !$=$ NODES)\\
\hspace*{1cm}	\{\\
\hspace*{2cm}		printf("Please only use 4 nodes or else modify NODES parameter$\backslash$n");\\
\hspace*{2cm}		MPI$\_$Abort(MCW, -1);\\
\hspace*{1cm}	\}\\
\hspace*{1cm}	if (rank $==$ root)\\
\hspace*{1cm}	\{\\
\hspace*{2cm}		for (x$ =$ 0; x $< $MATSIZE ; x$++$) //populating matrix with random values\\
\hspace*{2cm}		\{\\
\hspace*{3cm}			mat1[x] $=$ (rand() \% (MATSIZE$-$1)) $+$ 1 ;\\
\hspace*{2cm}		\}\\
\hspace*{2cm}		printf("Printing array$\backslash$n");\\
\hspace*{2cm}		for (x $= $0; x$ <$ MATSIZE ; x$++$) //printing\\
\hspace*{2cm}		\{\\
\hspace*{3cm}			printf("\%d$>$ \%d $\backslash$n", x, mat1[x]);\\
\hspace*{2cm}		\}\\
\hspace*{1cm}	\}\\

	//MPI$\_$Barrier(MCW);\\
\hspace*{1cm}	MPI$\_$Scatter($\&$mat1, MATSIZE/NODES, MPI$\_$INT, $\&$part, MATSIZE/NODES, MPI$\_$INT, root, MCW);\\
\hspace*{1cm}	//Assign Values to relevant buckets\\
\hspace*{1cm}	for (x $=$ 0; x $<$ MATSIZE/NODES ; x$++$ )\\
\hspace*{1cm}	\{\\
\hspace*{1cm}		bucket[part[x]/(MATSIZE/NODES)][x]  = part[x];
\hspace*{1cm}\}\\
	//Sorting Buckets internally\\
\hspace*{1cm}	for (x $=$ 0; x $<$ NODES; x$++$)
\hspace*{1cm}	\{\\
\hspace*{2cm}		for (y $=$ 0; y$ <$ MATSIZE/NODES ; y$++$ )\\
\hspace*{2cm}		\{\\
\hspace*{3cm}			for (z $= $y$+$1; z$ <$  MATSIZE/NODES ; z$++$ )\\
\hspace*{3cm}			\{\\
\hspace*{3.5cm}				if (bucket[x][y] $>$ bucket[x][z])\\
\hspace*{3.5cm}				\{\\
\hspace*{4cm}					tmp $=$ bucket[x][y];\\
\hspace*{4cm}					bucket[x][y]$ = $bucket[x][z];\\
\hspace*{4cm}					bucket[x][z] $=$ tmp;\\
\hspace*{3.5cm}				\}\\
\hspace*{3cm}		\}\\
\hspace*{2cm}	\}\\
\hspace*{1cm}\}\\
\hspace*{1cm}	MPI$\_$Alltoall(bucket, MATSIZE/NODES, MPI$\_$INT, bigbucket, MATSIZE/NODES, MPI$\_$INT, MCW);\\
\hspace*{1cm}	printf("\%d$>$Printing unsorted Big Buckets$\backslash$n", rank);\\	
\hspace*{1cm}	for (x $= $0; x $<$ MATSIZE; x$++$)\\
\hspace*{1cm}	\{\\
\hspace*{2cm}		printf("\%d$>$Bucket[\%d]$=$\%d$\backslash$n", rank, x, bigbucket[x]);\\
\hspace*{1cm}	\}\\

	//Sorting Big Buckets internally\\
\hspace*{1cm}	for (y $=$ 0; y $<$ MATSIZE ; y$++$ )\\
\hspace*{1cm}	\{\\
\hspace*{2cm}		for (z $=$ y$+$1; z $< $ MATSIZE; z$++$ )\\
\hspace*{2cm}		\{\\
\hspace*{3cm}			if (bigbucket[y]$ >$ bigbucket[z])\\
\hspace*{3cm}			\{\\
\hspace*{3.5cm}				tmp $=$ bigbucket[y];\\
\hspace*{3.5cm}				bigbucket[y] $=$ bigbucket[z];\\
\hspace*{3.5cm}				bigbucket[z] $=$ tmp;\\
\hspace*{3cm}			\}\\
\hspace*{2cm}		\}\\
\hspace*{1cm}	\}\\
\hspace*{1cm}	printf("\%d$>$Printing SORTED Big Buckets$\backslash$n", rank);\\	
\hspace*{1cm}	for (x $=$ 0; x $< $MATSIZE; x$++$)\\
\hspace*{1cm}\{\\
\hspace*{2cm}		printf("\%d$>$Bucket[\%d]$=$ \%d $\backslash$n", rank, x, bigbucket[x]);\\
\hspace*{1cm}	\}\\
\hspace*{1cm}	MPI$\_$Gather($\&$bigbucket, MATSIZE, MPI$\_$INT, $\&$mat2, MATSIZE, MPI$\_$INT, root, MCW);\\	
\hspace*{1cm}	if (rank $==$ root)\\
\hspace*{1cm}	\{\\
\hspace*{2cm}		printf("Printing Gathered Results$\backslash$n");\\
\hspace*{2cm}		for (x $= $0, y $=$ 0; x $<$ MATSIZE*NODES ; x$++$) //printing\\
\hspace*{2cm}		\{\\
\hspace*{3cm}			printf("\%d$>$ \%d $\backslash$n", x, mat2[x]);\\
\hspace*{3cm}			//trimming results\\
\hspace*{3cm}			if (mat2[x] !$=$ 0)\\
\hspace*{3cm}			\{\\
\hspace*{3.5cm}				mat1[y$++$] $=$ mat2[x];\\
\hspace*{3cm}			\}\\
\hspace*{2cm}		\}\\
\hspace*{2cm}		printf("Printing Sorted Gathered Results$\backslash$n");\\
\hspace*{2cm}		for (x $=$ 0; x $<$ MATSIZE ; x$++$)\\
\hspace*{2cm} 	\{\\
\hspace*{3cm}			printf("\%d$>$ \%d $\backslash$n", x, mat1[x]);\\
\hspace*{2cm}		\}	\\
\hspace*{1cm}	\}\\
\hspace*{1cm}	MPI$\_$Finalize();\\
\hspace*{1cm}	return 0;\\
\}\\
\end{enumerate}